home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / ABUSESRC.ZIP / AbuseSrc / imlib / decoder.c < prev    next >
C/C++ Source or Header  |  1996-04-11  |  12KB  |  394 lines
  1. /* DECODE.C - An LZW decoder for GIF
  2.  * Copyright (C) 1987, by Steven A. Bennett
  3.  *
  4.  * Permission is given by the author to freely redistribute and include
  5.  * this code in any program as long as this credit is given where due.
  6.  *
  7.  * In accordance with the above, I want to credit Steve Wilhite who wrote
  8.  * the code which this is heavily inspired by...
  9.  *
  10.  * GIF and 'Graphics Interchange Format' are trademarks (tm) of
  11.  * Compuserve, Incorporated, an H&R Block Company.
  12.  *
  13.  * Release Notes: This file contains a decoder routine for GIF images
  14.  * which is similar, structurally, to the original routine by Steve Wilhite.
  15.  * It is, however, somewhat noticably faster in most cases.
  16.  *
  17.  */
  18.  
  19. /*#include "std.h" */
  20. #include "errs.h"
  21. #include "image.hpp"
  22. #include "macs.hpp"
  23. #include <stdio.h>
  24. FILE *ufp;
  25.  
  26. /*IMPORT TEXT *malloc();  */               /* Standard C library allocation */
  27.  
  28. /* IMPORT INT get_byte()
  29.  *
  30.  *   - This external (machine specific) function is expected to return
  31.  * either the next byte from the GIF file, or a negative number, as
  32.  * defined in ERRS.H.
  33.  */
  34.  
  35. /* IMPORT INT out_line(pixels, linelen)
  36.  *     UBYTE pixels[];
  37.  *     INT linelen;
  38.  *
  39.  *   - This function takes a full line of pixels (one byte per pixel) and
  40.  * displays them (or does whatever your program wants with them...).  It
  41.  * should return zero, or negative if an error or some other event occurs
  42.  * which would require aborting the decode process...  Note that the length
  43.  * passed will almost always be equal to the line length passed to the
  44.  * decoder function, with the sole exception occurring when an ending code
  45.  * occurs in an odd place in the GIF file...  In any case, linelen will be
  46.  * equal to the number of pixels passed...
  47.  */
  48. /*IMPORT INT out_line(); */
  49.  
  50. /* IMPORT INT bad_code_count;
  51.  *
  52.  * This value is the only other global required by the using program, and
  53.  * is incremented each time an out of range code is read by the decoder.
  54.  * When this value is non-zero after a decode, your GIF file is probably
  55.  * corrupt in some way...
  56.  */
  57. int bad_code_count;
  58.  
  59. #define MAX_CODES   4095
  60.  
  61. /* Static variables */
  62. short curr_size;                     /* The current code size */
  63. short clear;                         /* Value for a clear code */
  64. short ending;                        /* Value for a ending code */
  65. short newcodes;                      /* First available code */
  66. short top_slot;                      /* Highest code for current size */
  67. short slot;                          /* Last read code */
  68.  
  69. /* The following static variables are used
  70.  * for seperating out codes
  71.  */
  72. short navail_bytes = 0;              /* # bytes left in block */
  73. short nbits_left = 0;                /* # bits left in current byte */
  74.   unsigned char b1;                           /* Current byte */
  75.   unsigned char byte_buff[257];               /* Current block */
  76.   unsigned char *pbytes;                      /* Pointer to next byte in block */
  77.  
  78.   long code_mask[13] = {
  79.      0,
  80.      0x0001, 0x0003,
  81.      0x0007, 0x000F,
  82.      0x001F, 0x003F,
  83.      0x007F, 0x00FF,
  84.      0x01FF, 0x03FF,
  85.      0x07FF, 0x0FFF
  86.      };
  87.  
  88.  
  89. /* This function initializes the decoder for reading a new image.
  90.  */
  91. short init_exp(short size)
  92.    {
  93.    curr_size = size + 1;
  94.    top_slot = 1 << curr_size;
  95.    clear = 1 << size;
  96.    ending = clear + 1;
  97.    slot = newcodes = ending + 1;
  98.    navail_bytes = nbits_left = 0;
  99.    return(0);
  100.    }
  101.  
  102. /* get_next_code()
  103.  * - gets the next code from the GIF file.  Returns the code, or else
  104.  * a negative number in case of file errors...
  105.  */
  106.  
  107. short int get_byte()
  108. {
  109.   short int x=0;
  110.   if (fread(&x,1,1,ufp)!=1)
  111.     return READ_ERROR;
  112.   else return x;
  113. }
  114.  
  115. short get_next_code()
  116.    {
  117.    short i, x;
  118.    unsigned long ret;
  119.  
  120.    if (nbits_left == 0)
  121.       {
  122.       if (navail_bytes <= 0)
  123.      {
  124.  
  125.      /* Out of bytes in current block, so read next block
  126.       */
  127.      pbytes = byte_buff;
  128.      if ((navail_bytes = get_byte()) < 0)
  129.         return(navail_bytes);
  130.      else if (navail_bytes)
  131.         {
  132.         for (i = 0; i < navail_bytes; ++i)
  133.            {
  134.            if ((x = get_byte()) < 0)
  135.           return(x);
  136.            byte_buff[i] = x;
  137.            }
  138.         }
  139.      }
  140.       b1 = *pbytes++;
  141.       nbits_left = 8;
  142.       --navail_bytes;
  143.       }
  144.  
  145.    ret = b1 >> (8 - nbits_left);
  146.    while (curr_size > nbits_left)
  147.       {
  148.       if (navail_bytes <= 0)
  149.      {
  150.  
  151.      /* Out of bytes in current block, so read next block
  152.       */
  153.      pbytes = byte_buff;
  154.      if ((navail_bytes = get_byte()) < 0)
  155.         return(navail_bytes);
  156.      else if (navail_bytes)
  157.         {
  158.         for (i = 0; i < navail_bytes; ++i)
  159.            {
  160.            if ((x = get_byte()) < 0)
  161.           return(x);
  162.            byte_buff[i] = x;
  163.            }
  164.         }
  165.      }
  166.       b1 = *pbytes++;
  167.       ret |= b1 << nbits_left;
  168.       nbits_left += 8;
  169.       --navail_bytes;
  170.       }
  171.    nbits_left -= curr_size;
  172.    ret &= code_mask[curr_size];
  173.    return((short)(ret));
  174.    }
  175.  
  176.  
  177. /* The reason we have these seperated like this instead of using
  178.  * a structure like the original Wilhite code did, is because this
  179.  * stuff generally produces significantly faster code when compiled...
  180.  * This code is full of similar speedups...  (For a good book on writing
  181.  * C for speed or for space optomisation, see Efficient C by Tom Plum,
  182.  * published by Plum-Hall Associates...)
  183.  */
  184.   unsigned char stack[MAX_CODES + 1];            /* Stack for storing pixels */
  185.   unsigned char suffix[MAX_CODES + 1];           /* Suffix table */
  186.   unsigned short prefix[MAX_CODES + 1];           /* Prefix linked list */
  187.  
  188. /* short decoder(linewidth)
  189.  *    short linewidth;               * Pixels per line of image *
  190.  *
  191.  * - This function decodes an LZW image, according to the method used
  192.  * in the GIF spec.  Every *linewidth* "characters" (ie. pixels) decoded
  193.  * will generate a call to out_line(), which is a user specific function
  194.  * to display a line of pixels.  The function gets it's codes from
  195.  * get_next_code() which is responsible for reading blocks of data and
  196.  * seperating them into the proper size codes.  Finally, get_byte() is
  197.  * the global routine to read the next byte from the GIF file.
  198.  *
  199.  * It is generally a good idea to have linewidth correspond to the actual
  200.  * width of a line (as specified in the Image header) to make your own
  201.  * code a bit simpler, but it isn't absolutely necessary.
  202.  *
  203.  * Returns: 0 if successful, else negative.  (See ERRS.H)
  204.  *
  205.  */
  206.  
  207. short decode_gif_data(image *im, FILE *fp)
  208.  
  209.    {
  210.    register unsigned char *sp, *bufptr;
  211.    unsigned char *buf;
  212.    register short code, fc, oc, bufcnt;
  213.    short c, size, ret,y;
  214.    ufp=fp;
  215.    /* Initialize for decoding a new image...
  216.     */
  217.    if ((size = get_byte()) < 0)
  218.       return(size);
  219.    if (size < 2 || 9 < size)
  220.       return(BAD_CODE_SIZE);
  221.    init_exp(size);
  222.  
  223.    /* Initialize in case they forgot to put in a clear code.
  224.     * (This shouldn't happen, but we'll try and decode it anyway...)
  225.     */
  226.    oc = fc = 0;
  227.  
  228.    /* Allocate space for the decode buffer
  229.     */
  230.    buf=im->scan_line(0);  y=0;
  231. /*   if ((buf = (unsigned char *)malloc(linewidth + 1)) == NULL)
  232.       return(OUT_OF_MEMORY); */
  233.  
  234.    /* Set up the stack pointer and decode buffer pointer
  235.     */
  236.    sp = stack;
  237.    bufptr = buf;
  238.    bufcnt = im->height();
  239.  
  240.    /* This is the main loop.  For each code we get we pass through the
  241.     * linked list of prefix codes, pushing the corresponding "character" for
  242.     * each code onto the stack.  When the list reaches a single "character"
  243.     * we push that on the stack too, and then start unstacking each
  244.     * character for output in the correct order.  Special handling is
  245.     * included for the clear code, and the whole thing ends when we get
  246.     * an ending code.
  247.     */
  248.    while ((c = get_next_code()) != ending)
  249.       {
  250.  
  251.       /* If we had a file error, return without completing the decode
  252.        */
  253.       if (c < 0)
  254.      {
  255. //     free(buf);
  256.      return(0);
  257.      }
  258.  
  259.       /* If the code is a clear code, reinitialize all necessary items.
  260.        */
  261.       if (c == clear)
  262.      {
  263.      curr_size = size + 1;
  264.      slot = newcodes;
  265.      top_slot = 1 << curr_size;
  266.  
  267.      /* Continue reading codes until we get a non-clear code
  268.       * (Another unlikely, but possible case...)
  269.       */
  270.      while ((c = get_next_code()) == clear)
  271.         ;
  272.  
  273.      /* If we get an ending code immediately after a clear code
  274.       * (Yet another unlikely case), then break out of the loop.
  275.       */
  276.      if (c == ending)
  277.         break;
  278.  
  279.      /* Finally, if the code is beyond the range of already set codes,
  280.       * (This one had better NOT happen...  I have no idea what will
  281.       * result from this, but I doubt it will look good...) then set it
  282.       * to color zero.
  283.       */
  284.     CONDITION(c<slot,"Error occured while reading gif");
  285.      if (c >= slot)
  286.         c = 0;
  287.  
  288.      oc = fc = c;
  289.  
  290.      /* And let us not forget to put the char into the buffer... And
  291.       * if, on the off chance, we were exactly one pixel from the end
  292.       * of the line, we have to send the buffer to the out_line()
  293.       * routine...
  294.       */
  295.      *bufptr++ = c;
  296.      if (--bufcnt == 0)
  297.         {
  298.  
  299. //        if ((ret = out_line(buf, linewidth)) < 0)
  300. //           {
  301. //           free(buf);
  302. //           return(ret);
  303. //           }
  304.         y++;
  305.         if (y<im->height())
  306.           buf=im->scan_line(y);
  307.         bufptr = buf;
  308.         bufcnt = im->width()-1;
  309.         }
  310.      }
  311.       else
  312.      {
  313.  
  314.      /* In this case, it's not a clear code or an ending code, so
  315.       * it must be a code code...  So we can now decode the code into
  316.       * a stack of character codes. (Clear as mud, right?)
  317.       */
  318.      code = c;
  319.  
  320.      /* Here we go again with one of those off chances...  If, on the
  321.       * off chance, the code we got is beyond the range of those already
  322.       * set up (Another thing which had better NOT happen...) we trick
  323.       * the decoder into thinking it actually got the last code read.
  324.       * (Hmmn... I'm not sure why this works...  But it does...)
  325.       */
  326.  
  327.      if (code >= slot)
  328.         {
  329.         if (code > slot)
  330.            ++bad_code_count;
  331.         code = oc;
  332.         *sp++ = fc;
  333.         }
  334.  
  335.      /* Here we scan back along the linked list of prefixes, pushing
  336.       * helpless characters (ie. suffixes) onto the stack as we do so.
  337.       */
  338.      while (code >= newcodes)
  339.         {
  340.         *sp++ = suffix[code];
  341.         code = prefix[code];
  342.         }
  343.  
  344.      /* Push the last character on the stack, and set up the new
  345.       * prefix and suffix, and if the required slot number is greater
  346.       * than that allowed by the current bit size, increase the bit
  347.       * size.  (NOTE - If we are all full, we *don't* save the new
  348.       * suffix and prefix...  I'm not certain if this is correct...
  349.       * it might be more proper to overwrite the last code...
  350.       */
  351.      *sp++ = code;
  352.      if (slot < top_slot)
  353.         {
  354.         suffix[slot] = fc = code;
  355.         prefix[slot++] = oc;
  356.         oc = c;
  357.         }
  358.      if (slot >= top_slot)
  359.         if (curr_size < 12)
  360.            {
  361.            top_slot <<= 1;
  362.            ++curr_size;
  363.            }
  364.  
  365.      /* Now that we've pushed the decoded string (in reverse order)
  366.       * onto the stack, lets pop it off and put it into our decode
  367.       * buffer...  And when the decode buffer is full, write another
  368.       * line...
  369.       */
  370.      while (sp > stack)
  371.         {
  372.         *bufptr++ = *(--sp);
  373.         if (--bufcnt == 0)
  374.            {
  375. /*           if ((ret = out_line(buf, linewidth)) < 0)
  376.           {
  377.           free(buf);
  378.           return(ret);
  379.           } */
  380.            y++;
  381.            if (y<im->height())
  382.          buf=im->scan_line(y);
  383.  
  384.            bufptr = buf;
  385.            bufcnt = im->width()-1;
  386.            }
  387.         }
  388.      }
  389.       }
  390.    ret = 0;
  391.    return(ret);
  392.    }
  393.  
  394.